package day_02.sort;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {10, 6, 5, 9, 8, 4, 3, 7, 1, 2};
        sort(arr);
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }

    private static void sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    // 对arr[l...r]范围排序
    private static void mergeSort(int[] arr, int l, int r) {
        if(l >= r) return;
        int mid = (r + l)/2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    //merge arr[l, mid] & arr[mid+1, r]
    private static void merge(int[] arr, int l, int mid, int r) {
//        int[] aux = new int[r - l +1];
//        for (int i = l; i <= r; i++) {
//            aux[i-l] = arr[i];
//        }
//
//        int i = l, j = mid+1;
//        for (int k = l; k <= r; k++) {
//            if(i > mid){
//                arr[k] = aux[j-l];
//                j++;
//            }else if(j > r){
//                arr[k] = aux[i-l];
//                i++;
//            }else if(aux[i-l] < aux[j-l]){
//                arr[k] = aux[i-l];
//                i++;
//            }else {
//                arr[k] = aux[j-l];
//                j++;
//            }
//        }
    }
}
